/**
 * Created by L.jp
 * Description:给出两个字符串 s 和 t，要求在 s 中找出最短的包含 t 中所有字符的连续子串。
 * User: 86189
 * Date: 2022-09-30
 * Time: 23:54
 */
public class Solution {
    boolean check(int[] hash) { //检查是否有⼩于0的
        for (int i = 0; i < hash.length; i++) {
            if (hash[i] < 0) return false;
        }
        return true;
    }
    public String minWindow (String S, String T) {
        int cnt = S.length() + 1;
        int[] hash = new int[128]; //记录⽬标字符串T的字符个数
        for(int i = 0; i < T.length(); i++)
            hash[T.charAt(i)] -= 1; //初始化哈希表都为负数，找的时候再加为正
        int slow = 0, fast = 0;
        int left = -1, right = -1; //记录左右区间
        for (; fast < S.length(); fast++) {
            char c = S.charAt(fast);
            //⽬标字符匹配+1
            hash[c]++;
            while (check(hash)) { //没有⼩于0的说明都覆盖了，缩⼩窗⼝
                if (cnt > fast - slow + 1) { //取最优解
                    cnt = fast - slow + 1;
                    left = slow;
                    right = fast;
                }
                c = S.charAt(slow);
                hash[c]--; //缩⼩窗⼝的时候减1
                slow++; //窗⼝缩⼩
            }
        }
        if (left == -1) //找不到的情况
            return "";
        return S.substring(left, right + 1);
    }
}
